The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We present an extension of Wiener’s attack on small RSA secret decryption exponents [10]. Wiener showed that every RSA public key tuple (N,e) with $e \in {\mathbb{Z}}_{\phi(N)}^*$ that satisfies ed − 1 = 0 mod φ(N) for some yields the factorization of N=pq. Our new method finds p and q in polynomial time for every (N,e) satisfying ex + y = 0 mod φ(N) with ...
We describe a cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem, published at Eurocrypt 2003 by Augot and Finiasz. Given the public-key and a ciphertext, we recover the corresponding plaintext in polynomial time. Our technique is a variant of the Berlekamp-Welsh algorithm. We also describe a cryptanalysis of the reparation published by the authors on the...
Let E be an elliptic curve defined over . The inverse operation of point doubling, called point halving, can be done up to three times as fast as doubling. Some authors have therefore proposed to perform a scalar multiplication by an “halve-and-add” algorithm, which is faster than the classical double-and-add method. If the coefficients of the equation defining the curve...
We propose a scalar multiplication algorithm for elliptic and hyperelliptic curve cryptosystems, which uses affine arithmetic and is resistant against simple power attacks. Also, using a modification of known techniques the algorithm can be made immune against differential power attacks. The algorithm uses Montgomery’s trick and a precomputed table consisting of multiples of the base point. Consequently,...
In this paper we present a fast addition algorithm in the Jacobian of a Picard curve over a finite field of characteristic different from 3. This algorithm has a nice geometric interpretation, comparable to the classic ”chord and tangent” law for the elliptic curves. Computational cost for addition is 144M + 12SQ + 2I and 158M + 16SQ + 2I for doubling.
We present a new undeniable signature scheme which is based on the computation of characters. Our signature scheme offers the advantage of having an arbitrarily short signature. Its asymptotic complexity is attractive: the asymptotic complexity of all algorithms (even the key setup) are quadratic in the size of the modulus n in bits when the other parameters are fixed. The practical complexity can...
Universal Designated-Verifier Signature (UDVS) schemes are digital signature schemes with additional functionality which allows any holder of a signature to designate the signature to any desired designated-verifier such that the designated-verifier can verify that the message was signed by the signer, but is unable to convince anyone else of this fact. Since UDVS schemes reduce to standard...
In this paper, we provide the first committed signature provably secure in the standard complexity model based on the strong RSA assumption. The idea behind the construction is that given any valid partial signature of message m, if a co-signer with its auxiliary input is able to generate variables called the resolution of message m such that the distribution of the variables is indistinguishable...
A group key agreement protocol allows a set of users, communicating over a public network, to agree on a private session key. Most of the schemes proposed so far require a linear number (with respect to the number of participants) of communication rounds to securely achieve this goal. In this paper we propose a new constant-round group key exchange protocol that provides efficiency and privacy under...
In modern collaborative and distributed applications, authenticated group key agreement (GKA) is one of important issues. Recently identity (ID)-based authenticated GKA has been increasingly researched because of the simplicity of a public key management. In this paper, we present a formal treatment on ID-based authenticated GKA, which extends the standard GKA model. We present two GKA protocols which...
Schemes for encrypted key exchange are designed to provide two entities communicating over a public network, and sharing a (short) password only, with a session key to be used to achieve data integrity and/or message confidentiality. An example of a very efficient and “elegant” scheme for encrypted key exchange considered for standardization by the IEEE P1363 Standard working group is AuthA. This...
We generalize and extend results obtained by Boneh and Venkatesan in 1996 and by González Vasco and Shparlinski in 2000 on the hardness of computing bits of the Diffie-Hellman key, given the public values. Specifically, while these results could only exclude (essentially) error-free predictions, we here exclude any non-negligible advantage, though for larger fractions of the bits. We can also demonstrate...
In this paper, we study short exponent Diffie-Hellman problems, where significantly many lower bits are zeros in the exponent. We first prove that the decisional version of this problem is as hard as two well known hard problems, the standard decisional Diffie-Hellman problem (DDH) and the short exponent discrete logarithm problem. It implies that we can improve the efficiency of ElGamal scheme and...
This paper proposes a new public key authenticated encryption (signcryption) scheme based on the Diffie-Hellman problem in Gap Diffie-Hellman groups. This scheme is built on the scheme proposed by Boneh, Lynn and Shacham in 2001 to produce short signatures. The idea is to introduce some randomness into this signature to increase its level of security in the random oracle model and to re-use that randomness...
The problem MQ of solving a system of multivariate quadratic equations over a finite field is relevant to the security of AES and for several public key cryptosystems. For example Sflash, the fastest known signature scheme (cf. [1]), is based on MQ equations over GF(27), and Patarin’s 500 $ HFE Challenge 2 is over GF(24). Similarly, the fastest alleged algebraic attack on AES due to Courtois, Pieprzyk,...
We consider RSA-type schemes with modulus N=prq for r ≥ 2. We present two new attacks for small secret exponent d. Both approaches are applications of Coppersmith’s method for solving modular univariate polynomial equations [5]. From these new attacks we directly derive partial key exposure attacks, i.e. attacks when the secret exponent is not necessarily...
Strong notions of security for unconditionally secure digital signature schemes (USDS) were recently proposed where security is defined based on notions of security in computationally–secure digital signatures. The traditional area of unconditionally secure authentication, however, is that of “authentication codes” (A–codes). Relations between primitives is central to cryptographic research. To this...
In this paper, we first formalize the concept of ID-based identification scheme. Secondly, we show a transformation from any digital signature scheme satisfying certain condition to an ID-based identification scheme. As an instance, we present the first provably secure ID-based identification scheme based on the hardness of discrete logarithm problem. (More precisely, the hardness of gap Diffie-Hellman...
In this paper, we examine issues related to the construction of identity-based threshold decryption schemes and argue that it is important in practice to design an identity-based threshold decryption scheme in which a private key associated with an identity is shared. A major contribution of this paper is to construct the first identity-based threshold decryption scheme secure against chosen-ciphertext...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.